package oj;

public class LC76 {
    public String minWindow(String s, String t) {
        if(s.length()==0 || t.length()==0 ||s.length()<t.length()){
            return "";
        }
        int[] winFreq=new int[128];//s的子串的字频数组
        int[] tFreq=new int[128];//t的子串的字频数组
        char[] sc=s.toCharArray();
        char[] tc=t.toCharArray();
        for(int i=0;i<tc.length;i++){
            tFreq[tc[i]]++;
        }
        int distance=0;//表示滑动窗口内部包含了T中字符的个数，窗口内单个字符个数等于T中对应的字符个数时不再增加
        int begin=0;//最小覆盖字串的起始下标
        int len=s.length()+1;//最小覆盖子串的长度
        int left=0;
        int right=0;
        while(right<sc.length){
            if(tFreq[sc[right]]==0){
                right++;
                continue;
            }
            if(winFreq[sc[right]]<tFreq[sc[right]]){
                distance++;
            }
            winFreq[sc[right]]++;
            right++;

            while(distance==tc.length){
                if(right-left<len){
                    len=right-left;
                    begin=left;
                }
                if(tFreq[sc[left]]==0){
                    left++;
                    continue;
                }
                if(winFreq[sc[left]]==tFreq[sc[left]]){
                    distance--;
                }
                winFreq[sc[left]]--;
                left++;
            }
        }
        if(len==s.length()+1){
            return "";
        }
        return s.substring(begin,begin+len);
    }
}